//
// Created by zhulingfeng on 2020/2/6.
//
#include "create_binary_tree.hpp"
#include <cctype>
#include <queue>
#include <stdexcept>

int CharToDigit(const char c) {
  if (!isdigit(c)) {
    throw std::invalid_argument("Input char should be a digit.");
  }
  return c - '0';
}

BinaryTreeNode *CreateBTFromLevelOrder(const std::string &s) {
  for (const auto c : s) {
    if (c != '#' && !isdigit(c)) {
      throw std::invalid_argument("Contains invalid character in input: " +
                                  std::string(1, c));
    }
  }

  if (s.empty()) return nullptr;
  if (s[0] == '#') return nullptr;
  auto root = new BinaryTreeNode(CharToDigit(s[0]));
  std::queue<BinaryTreeNode *> q;
  q.push(root);
  for (int i = 1; i < s.size(); i++) {
    auto node = q.front();
    q.pop();
    if (s[i] != '#') {
      node->left_ = new BinaryTreeNode(CharToDigit(s[i]));
      q.push(node->left_);
    }
    i++;
    if (i >= s.size()) break;
    if (s[i] != '#') {
      node->right_ = new BinaryTreeNode(CharToDigit(s[i]));
      q.push(node->right_);
    }
  }
  return root;
}

BinaryTreeNode *CreateBTFromPreOrder(const std::string &s, int &index) {
  if (index >= s.size()) return nullptr;
  char c = s[index];
  if (c == '#') return nullptr;
  auto root = new BinaryTreeNode(CharToDigit(c));
  root->left_ = CreateBTFromPreOrder(s, ++index);
  root->right_ = CreateBTFromPreOrder(s, ++index);
  return root;
}

BinaryTreeNode *CreateBTFromPreOrder(const std::string &s) {
  int index = 0;
  CreateBTFromPreOrder(s, index);
}

BinaryTreeNode *CreateBTFromPostOrder(const std::string &s, int &index) {
  if (index < 0) return nullptr;
  char c = s[index];
  if (c == '#') return nullptr;
  auto root = new BinaryTreeNode(CharToDigit(c));
  root->right_ = CreateBTFromPostOrder(s, --index);
  root->left_ = CreateBTFromPostOrder(s, --index);
  return root;
}
BinaryTreeNode *CreateBTFromPostOrder(const std::string &s) {
  int index = static_cast<int>(s.size() - 1);
  CreateBTFromPostOrder(s, index);
}

BinaryTreeNode *CreateBTFromPreAndInOrder(const std::vector<int> &pre,
                                          const std::vector<int> &in,
                                          int pre_begin, int pre_end,
                                          int in_begin, int in_end) {
  if (pre_begin == pre_end) return nullptr;
  // Find root index in in-order.
  int root_index = in_begin;
  for (; root_index < in_end; root_index++) {
    if (in[root_index] == pre[pre_begin]) break;
  }
  if (root_index >= in_end) {
    throw std::invalid_argument("Can not find root val in in-order.\n");
  }

  auto root = new BinaryTreeNode(pre[pre_begin]);
  // Recursively construct subtree.
  int pre_left_begin = pre_begin + 1;
  int pre_left_end = pre_left_begin + root_index - in_begin;
  root->left_ = CreateBTFromPreAndInOrder(pre, in, pre_left_begin, pre_left_end,
                                          in_begin, root_index);
  root->right_ = CreateBTFromPreAndInOrder(pre, in, pre_left_end, pre_end,
                                           root_index + 1, in_end);
  return root;
}

BinaryTreeNode *CreateBTFromPreAndInOrder(const std::vector<int> &pre,
                                          const std::vector<int> &in) {
  if (pre.size() != in.size())
    throw std::invalid_argument(
        "Pre-order and in-order data should have same "
        "size.");
  return CreateBTFromPreAndInOrder(pre, in, 0, pre.size(), 0, in.size());
}

void GetPostFromPreAndInOrder(const std::vector<int> &pre,
                              const std::vector<int> &in,
                              std::vector<int> &post, int pre_begin,
                              int pre_end, int in_begin, int in_end,
                              int post_begin, int post_end) {
  if (pre_begin == pre_end) return;
  // Find root index in in-order.
  int root_index = in_begin;
  for (; root_index < in_end; root_index++) {
    if (in[root_index] == pre[pre_begin]) break;
  }
  if (root_index >= in_end) {
    throw std::invalid_argument("Can not find root val in in-order.\n");
  }

  int pre_left_begin = pre_begin + 1;
  int left_length = root_index - in_begin;
  int pre_left_end = pre_left_begin + left_length;
  int post_left_end = post_begin + left_length;
  int post_right_end = post_end - 1;
  post[post_right_end] = pre[pre_begin];
  GetPostFromPreAndInOrder(pre, in, post, pre_left_begin, pre_left_end,
                           in_begin, root_index, post_begin, post_left_end);
  GetPostFromPreAndInOrder(pre, in, post, pre_left_end, pre_end, root_index + 1,
                           in_end, post_left_end, post_end - 1);
}

void GetPostFromPreAndInOrder(const std::vector<int> &pre,
                              const std::vector<int> &in,
                              std::vector<int> &post) {
  if (pre.size() != in.size())
    throw std::invalid_argument(
        "Pre-order and in-order data should have same "
        "size.");
  int n = static_cast<int>(pre.size());
  post.resize(n);
  GetPostFromPreAndInOrder(pre, in, post, 0, n, 0, n, 0, n);
}

std::vector<int> GetPostFromPreAndInOrder(const std::vector<int> &pre,
                                          const std::vector<int> &in) {
  std::vector<int> post;
  GetPostFromPreAndInOrder(pre, in, post);
  return post;
}
